package ufcg.metci.huffman;

import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Stack;

/**
 * Projeto para disciplina de Metodologia Científica - UFCG - 2012.1
 * 
 * @author Ana Clara Lacerda
 * @author Rodolfo Marinho
 * 
 * Esta classe contém algoritmos do huffman que são
 * utilizados tanto na compressão quando na descompressão
 *
 */
public abstract class Huffman {
	
	protected PriorityQueue<HuffmanNode> nodesQueue;
	
	protected int numberOfSymbols;
	
	protected List<HuffmanNode> nodes = new ArrayList<HuffmanNode>();
	protected List<String> foundSymbols = new ArrayList<String>();

	/**
	 * Build the Huffman Tree
	 * @param frequency
	 * @return
	 */
	public HuffmanNode buildTree(int[] frequency) {
		nodesQueue = new PriorityQueue<HuffmanNode>();

		for (int i = 0; i < frequency.length; i++) {
			if (frequency[i] > 0) {
				nodesQueue.offer(new HuffmanLeaf(Character.toString((char) i),
						frequency[i])); // inicia a arvore apenas com folhas
			}
		}
		this.numberOfSymbols = nodesQueue.size();
		while (nodesQueue.size() > 1) {
			// recupera os dois nós de menor frequencia
			HuffmanNode tree1 = nodesQueue.poll();
			HuffmanNode tree2 = nodesQueue.poll();

			nodesQueue.offer(new HuffmanNode(tree1, tree2));
			// cria um novo nó com os dois recuperados acima e o insere novamente na fila
		}
		return nodesQueue.peek();
	}
	
	/**
	 * Generates the huffman code to each leaf
	 * 
	 * @param root
	 * @param code
	 */
	protected void buildCodes(HuffmanNode root, Stack<Byte> code) {
		if (root instanceof HuffmanLeaf) {
			HuffmanLeaf leaf = (HuffmanLeaf) root;

			String codeWord = "";
			for (int i = 0; i < code.size(); i++) {
				codeWord += code.get(i).byteValue();
			}
			leaf.setCode(codeWord);
			nodes.add(leaf);
			foundSymbols.add(leaf.getValue());
		} else {
			// Left code = 0
			code.push(new Byte((byte) 0));
			buildCodes(root.getLeft(), code);
			code.pop();

			// Right code = 1
			code.push(new Byte((byte) 1));
			buildCodes(root.getRight(), code);
			code.pop();
		}
	}
	
	public abstract String buildContent();

}
